As said above, extending TOOL with exceptions implied modifications at each level of the compiler, from the lexer to the code generator, not to mention the CAFEBABE library.
\subsection{Lexer \& parser}
Extending the syntax analyzer to accept the new grammar (see chapter \ref{ToolGrammarExtension}) is quite straightforward. 

The first point was to make the lexer aware of the new tokens, THROW, THROWS, TRY, CATCH and FINALLY. This part was the easiest.

Next came the parser, which we had to modify to accept the extended rule for method declaration, plus the other new statements. 
The parser also checks that \textsf{\small try} and \textsf{\small finally} statements aren't empty and that \textsf{\small try} statements are always accompanied by either at least one \textsf{\small catch} or one \textsf{\small finally}, accordingly with the grammar.

Of course, the AST also had to be extended. In particular, \textsf{\small MethDecl} now has a new field : \textsf{\small throws}, the potentially empty list of thrown exceptions.

It also has four new statements : 

\begin{itemize}

\item \textsf{\small TryCatchBlock}, which contains a body, a list of \textsf{\small catch} statements and a potentially nonexistent \textsf{\small finally} statement.

\item \textsf{\small Catch}, which contains both the type and the id of the exception begin caught (two \textsf{\small Identifier}) and a body.

\item \textsf{\small Finally}, which just contains a body.

\item \textsf{\small Throw}, which takes an \textsf{\small ExprTree} as parameter.

\end{itemize}

\subsection{Semantic analysis}

The analyzer is problably the part that was the most intensively modifed, not only were the symbol analyzer and the type checker modifed, but an exception checker was also added.

\subsubsection{Symbols}

As said above, \textsf{\small ToolException} is defined in Java, so as to separate Java exception hierarchy and TOOL's exception hierarchy. 
But since \textsf{\small ToolException} is also used in TOOL, the compiler needs to be aware of the existence of this class. 
This was done by adding the InitialGlobalScope.scala file to the project.
This file contains the list of all the classes defined outside of TOOL, along with a list of their attributes. 
The list of classes is initialized to this value at the beginning of the symbol analysis phase.

An \textsf{\small ExceptionSymbol} class, which extends \textsf{\small VariableSymbol} was added to \textsf{\small Symbols.scala}.
Also, a list of \textsf{\small ExceptionSymbol} was added to the \textsf{\small MethodSymbol} class, to represent the exceptions that can be thrown when this method is called.

\medskip

The symbol collection phase doesn't differ from the basic version of the compiler; new exceptions are just added to the class list and are considered as types.

The second phase of symbol analysis was a bit modified however. 
Since at this point, the compiler knows all the types defined in the program including all the different exceptions, it can assign the correct symbols to the list of identifiers contained in the \textsf{\small throws} part of each method declaration.
The symbol analysis for \textsf{\small finally} and \textsf{\small try} is straightforward : the analyzer just proceeds with their body.
It is a bit different for \textsf{\small catch} blocks however, because they add a new variable to the list of symbols (a reference to the exception being caught).
The compiler needs to do two things here : check that the identifier of this reference isn't already used, and if it is not the case, add it to the list, proceed with the body of the catch, and finally, remove it from the list (we don't want a reference to the exception to be available outside of the \textsf{\small catch} block).
When a \textsf{\small throw} statement is encountered, the analyzer just proceeds with the corresponding \textsf{\small ExprTree}.

\subsubsection{Type checking}

The modifications to the type checker are quite straightforward.
When a \textsf{\small throw} is encountered, the type checker ensures that the associated expression is throwable (\textit{i.e.} that the type of this expression is a subtype of \textsf{\small ToolException}).
It does the same checks for the identifiers in \textsf{\small throws} statements and in \textsf{\small catch} statements.

The body of the \textsf{\small catch}, \textsf{\small finally} and \textsf{\small try} statements are type-checked the same way as the other statements' bodies.

Note that no constraint was put on the overriding of method that throw exceptions\footnote{Unlike in Java, where an overriding method cannot throw a checked exception that cannot be thrown by the overriden method.}. We consider that it's the programmer's duty to know what will happen when he overrides a method.

\subsubsection{Exception checking}

The exception checker's duty is to verify that all exceptions are handled correctly.
All exceptions must either be caught in a \textsf{\small catch} statement, or the method where an exception may be raised must include that exception (or a superclass) in its \textsf{\small throws} list.

There are only two ways of raising an exception\footnote{TOOL doesn't know about unchecked exception classes}: either explicitely by using a \textsf{\small throw} or implicitely by calling a method whose \textsf{\small throws} list isn't empty.

The exception checker therefore traverses the AST tree looking for \textsf{\small throw} statements and method calls. 
The algorithm is fairly simple, it traverses the AST, keeping track of the list of checked exceptions ($L$ in the algorithm) :

\begin{itemize}
\item if the current node is a method definition, $L$ is set to the list of exception contained in \textsf{\small throws} and the body of the method is checked.
\item if the current node is a \textsf{\small try}, the list of exception types handled in the associated \textsf{\small catch}(es) is added to $L$ and the body of the try is checked with the new $L$, the checker then continues with the body of the \textsf{\small catch} and \textsf{\small finally} using the old $L$. 
\item if the current node is a throw, get the type of the raised exception, if neither this exception nor one of its superclass is contained in $L$, the code doesn't compile.
\item if the current node is a method call, get the list of exception contained in \textsf{\small throws}, and apply the same check as in the previous step to each of them.
\end{itemize}

This way, the compiler ensures that any exception is either caught or resent.

\subsection{Code generation}

The code generation part for this extension required a lot of ``reverse engineering'' : we disassembled several class files compiled with javac to understand how exceptions are handled.

\input{codegeneration}

\subsection{\label{Cafebabe}Cafebabe}

Two modifications were made to CAFEBABE : adding the \textsf{\small addHandler} method and modifiying the \textsf{\small computeMaxStackSize} method.
Fortunately, CAFEBABE already  supported exception tables, all that was left to do was to implement the \textsf{\small addHandler} method.
It was quite simple to do, a list of all the entries is kept inside \textsf{\small CodeHandler} and updated whenever the \textsf{\small addHandler} is called.
The real offsets of the entries are computed when the \textsf{\small freeze} method is called.

\medskip

The second modification involved the \textsf{\small computeMaxStackSize} method : this method wasn't designed to take exceptions into account.
In particular, it didn't analyze the handlers.
This led to a very nasty bug : if we hadn't made tests with large \textsf{\small catch} statements, we wouldn't have found it. 
The stack size is specified in the class file by the compiler, and re-verified by the JVM at load-time.
If the size found by the loader is bigger than the class file's, a \textsf{\small VerifyError} exception is raised, with the following message ``Stack size too big''.
But since the original \textsf{\small setHeight} method didn't take handlers into account such an exception was raised every time one of the handler's needed stack size was bigger than the stack size computed by \textsf{\small getMaxStackSize}. 
This bug was quite time consuming.

We had to make the following modifications to fix it : 

\begin{itemize}

\item analyze each of the handlers : the \textsf{\small setHeight} method is called with the address of the handler and 1 as arguments\footnote{When an exception is called, it is pushed on the stack, this is why the stack size is 1 at the start of an handler} for each handlers.

\item add a case for the \textsf{\small JSR} instruction in \textsf{\small setHeight} : \textsf{\small setHeight} is recursively called with stack size 1\footnote{The return addres is pushed on the stack} on the address passed to \textsf{\small JSR} as argument. It is then called on the next instruction with the same stack size as that of the \textsf{\small JSR} instruction.

\item add a case for the \textsf{\small ATHROW} instruction : \textsf{\small setHeight} should just stop when it encounters an \textsf{\small ATHROW}.

\end{itemize}
